// @题目描述
// 给定两个整数数组 inorder 和 postorder ，
// 其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

// @题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// @博文链接：https://blog.csdn.net/ITSOK_123/article/details/125029925

// 递归1（O(N),O(N)）
class Solution {
    // 前序遍历中树的节点值与下标值的map映射
    unordered_map<int,int> index;
public:
TreeNode* build(vector<int>& inorder,vector<int>& postorder,int inLeft,int inRight,int postLeft,int postRight){
        // 遍历列表为空返回空树
        if(inLeft>inRight){
            return nullptr;
        }
        // 记录后序遍历中的树的根节点以及中序遍历中的树的根节点
        int postRoot = postRight;
        int inorderRoot = index[postorder[postRoot]];
        // 构造一颗只有根节点的树
        TreeNode* root = new TreeNode(postorder[postRoot]);
        // 确定树的左子树的节点个数
        int leftSize = inorderRoot - inLeft;
		// 左子树构建
        root->left = build(inorder,postorder,inLeft,inorderRoot-1,postLeft,postLeft+leftSize-1);
		// 右子树构建
        root->right = build(inorder,postorder,inorderRoot+1,inRight,postLeft+leftSize,postRoot-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        size_t size = postorder.size();
		// 建立中序遍历节点值和下标map映射
        for(int i=0;i<size;i++){
            index[inorder[i]] = i;
        }
        if(size == 0) return nullptr;
        return build(inorder,postorder,0,size-1,0,size-1);
    }
};

// 递归2（O(N),O(N)）
class Solution {
    // 记录后序遍历中的根节点
    int postIndex;
    // 前序遍历中树的节点值与下标值的map映射
    unordered_map<int,int> index;
public:
TreeNode* build(vector<int>& inorder,vector<int>& postorder,int inLeft,int inRight) {
        // 遍历列表为空返回空树
        if(inLeft>inRight)  return nullptr;
        // 记录当前根节点值
        int rootVal = postorder[postIndex];
        // 构建只有根节点的树
        TreeNode* root = new TreeNode(rootVal);
        // 求出根节点在中序遍历中的下标值
        int rootIndex = index[rootVal];
        // 后序遍历根节点下标减一左移
        postIndex--;
        // 构建右子树，注意这里必须先构建右子树，
        // 否则在构建左子树的时候的postIndex--会错误移动
        // 由于遍历顺序的原因，后序中根节点左边最近的元素都处于右子树内
        root->right = build(inorder,postorder,rootIndex+1,inRight);
        // 构建左子树
        root->left = build(inorder,postorder,inLeft,rootIndex-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        size_t size = postorder.size();
        postIndex = size -1;
		// 建立中序遍历节点值和下标map映射
        for(int i=0;i<size;i++){
            index[inorder[i]] = i;
        }
        if(size == 0) return nullptr;
        return build(inorder,postorder,0,size-1);
    }
};

// 迭代（O(N),O(N)）
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        size_t size = postorder.size();
        // 空树的情况
        if(size == 0)   return nullptr;
        // 以size记录后序访问下标值
        size--;
        // 构造只有根节点的树
        TreeNode* root = new TreeNode(postorder[size]);
        stack<TreeNode*> st;
        // 根节点入栈
        st.push(root);
        // 中序访问下标
        int  inorderIndex = size;
        // 处理除根节点之外的节点
        while(size--){
            // 取新访问的后序遍历节点（从后往前）
            int postVal = postorder[size];
            // 取栈顶结点
            TreeNode* node = st.top();
            // 新的节点是栈顶结点的右孩子
            if(node->val != inorder[inorderIndex]){
                node->right = new TreeNode(postVal);
                st.push(node->right);
            }else{
                // 新的节点不是栈顶结点的孩子
                // 那就是栈顶结点的某个祖先的左孩子
                while(!st.empty() && st.top()->val == inorder[inorderIndex]){
                    node = st.top();
                    st.pop();
                    --inorderIndex;
                }
                node->left = new TreeNode(postVal);
                st.push(node->left);
            }
        }
        return root;
    }
};